#include <iostream>
#include <vector>

using namespace std;
class Solution
{
 public:
  bool exist(vector<vector<char>>& matrix, string str)
  {
    for (int i = 0; i < matrix.size(); i++)
      for (int j = 0; j < matrix[i].size(); j++)
      {
        if (dfs(matrix, str, 0, i, j))  // 从矩阵的[i,j]开始搜，0表示目前与字符串匹配的个数
          return true;
      }

    return false;
  }

  bool dfs(vector<vector<char>>& matrix, string& str, int u, int x, int j)
  {
    if (u == str.size()) return true;  // 已经全部搜索到
    if (matrix[x][y] != str[u]) return false;

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    char t = matrix[x][y];
    matrix[x][y] = '*';  // 不能走重复，所以替换

    // 深度搜索
    for (int i = 0; i < 4; i++)
    {
      int a = x + dx[i], b = y + dy[i];

      if (a >= 0 && a < matrix.size() && b >= 0 && b < matrix[a].size())  // 防止越界
      {
        if (dfs(matrix, str, u + 1, a, b)) return true;
      }
    }
    matrix[x][y] = t;
    return false;
  }
};

int main() {}